1. Field of the Invention
The present invention relates to content addressable memories, and more specifically, to a content addressable memory having an improved priority encoder.
2. Brief Description of the Related Art
Priority encoders are electronic logic circuits that determine which of a number of inputs has the highest or lowest priority. Priority encoders are used in a number of computer systems, as well as other applications. Priority encoders can be utilized in conjunction with a content addressable memory (CAM), for example.
A CAM is a memory device in which data is accessed based upon its content, rather than its storage address or location. A CAM generally includes multiple data storage locations comprising multiple memory cells. Contrary to DRAMs and SRAMs content addressable memories do not store data in any structured fashion. The locations at which data is stored within CAM can be merely random, where the data can be written directly into the first empty location within the CAM. Once data is stored in CAM, it can be found by comparing every bit in the CAM memory cells with data placed in a comparand register. Unlike random access memory (“RAM”), all data words in the storage locations of a CAM may be simultaneously compared with a search word stored in a comparand register. Data words stored in the CAM are compared with the search word. A match line is activated for each data word that matches the search word. If a match exists for every bit stored in a particular location within the CAM corresponding to every bit in the comparand, a match line is asserted. A priority encoder can then sort out which matching location among multiple match lines has the top priority. CAM devices are unique in that a user generally supplies the data and receives back an address for that data. Because the CAM does not require address lines to find data, the depth of the CAM can be extended as far as desired—well beyond the depth of a RAM.
A CAM device is useful in any application requiring fast searches of a database, lists, or pattern, and supplies heightened performance advantages over other memory search algorithms. Currently, CAMs are particularly well suited for handling packet protocols, such as TCP/IP protocols employed in packet processors that are used to route information across an intranet or the Internet.
In a typical application, a CAM may generate multiple match signals on active match lines in response to a search request. Typically, the match signals are sent to a priority encoder to determine the single address corresponding to the highest priority match.
A typical priority encoder has two stages. The first stage is a Highest Priority Indicator (HPI), which flags one output associated with the active input having the highest priority. A typical prior art HPI 2 is shown in FIG. 1. The second stage of the typical priority encoder is an address encoder, which converts the flag from the HPI into a binary number identifying the address of the flagged output.
Referring to FIG. 1, HPI 2 typically operates like a “thermometer” in determining which of the match results has the highest priority. Conventionally, match inputs from respective match lines in a CAM are applied to terminals 4, 6, 8, and 10, etc., of HPI 2. An enable signal is provided on line 12. When multiple matches are encountered, the match line located on the lowest segment of the HPI is given the highest priority, by convention. The match line that indicates a match on inputs 4, 6, 8, 10 and which has the highest priority will cause the lowest output terminal 14, 16, 18, 20 to change states, indicating a match.
As shown in FIG. 1, HPI 2 utilizes an arrangement of logic gates to determine which of the inputs has the highest priority. Each segment of HPI 2 includes a NOT gate, a NAND gate, and a NOR gate. Referring to FIG. 1, highest priority stage 30 includes NOT gate 32 which inverts enable input 12, and supplies it to NOR gate 34. NOR gate 34 also receives a signal on match line input 4. Enable input 12 is supplied to NAND gate 36, along with match line input 4. The result from NOR gate 34 is supplied on output terminal 14.
HPI 2 includes several such stages, of which four are shown in FIG. 1. Thus, the result from NAND gate 36 is supplied to the next logically lowest priority stage (physically higher on the “thermometer”) made up similarly of NOT gate 42, NOR gate 44, and NAND gate 46. NOR gate 44 supplies a signal to output terminal 16, and NAND gate 46 supplies its signal to the third lowest priority stage made up of NOT gate 52, NOR gate 54, and NAND gate 56. A similar fourth-lowest priority stage is shown which includes NOT gate 62, NOR gate 64, and NAND gate 66. Additional stages are indicated by the dashed result line provided on NAND gate 66.
In operation, matches are indicated on match lines 4, 6, 8, and 10 as logic 0, enable signal 12 having a logic high. Thus, in the first stage 30, if match line 4 is low, output 14 will be high, indicating a highest priority match on line 4. HPI 2 thus provides a single highest priority match.
In certain applications, it may be desirable to encode more than one highest priority input. For example, in CAMs, the comparand data bits are implemented such that a comparison can be made for a logic state of 1, a logic state of 0, or a “don't care” state wherein bits in the comparand register are masked as not to be involved in the matching search. A match is declared regardless of what state is in the respective “don't care” bits in the CAM words. These “don't care” bits are used typically in a search known in the art as a search for the longest match. As a result of a search for the longest match, multiple words in the CAM may match the un-masked data bits in the comparand register. In such a typical application, a special multi-match detection circuit indicates the presence of multiple matches. Using a typical prior art priority encoder, only one match, the one with the highest priority, is recorded. In order to determine the next highest priority match, the user must discard the highest priority match, and re-encode the CAM match results to obtain the next highest priority match. Such manual manipulation of the CAM results is time consuming and inefficient. It is desirable, instead, to find the identity of all the matching words.
A priority encoder is needed that can automatically successively encode by priority multiple matches in a CAM.